package lc20240604;

import java.util.*;

/**
  * @description 399. 除法求值。
  * @author 不知名帅哥
  * @date 2024/6/4 23:28
  * @version 1.0
*/
public class EvaluateDivision {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 构建图结构
        Map<String, Map<String, Double>> graph = new HashMap<>();
        
        for (int i = 0; i < equations.size(); i++) {
            String A = equations.get(i).get(0);
            String B = equations.get(i).get(1);
            double value = values[i];
            
            graph.putIfAbsent(A, new HashMap<>());
            graph.putIfAbsent(B, new HashMap<>());
            
            graph.get(A).put(B, value);
            graph.get(B).put(A, 1.0 / value);
        }
        
        // 处理查询
        double[] results = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String C = queries.get(i).get(0);
            String D = queries.get(i).get(1);
            
            if (!graph.containsKey(C) || !graph.containsKey(D)) {
                results[i] = -1.0;
            } else if (C.equals(D)) {
                results[i] = 1.0;
            } else {
                Set<String> visited = new HashSet<>();
                results[i] = dfs(graph, C, D, visited);
            }
        }
        
        return results;
    }
    
    private double dfs(Map<String, Map<String, Double>> graph, String start, String end, Set<String> visited) {
        if (graph.get(start).containsKey(end)) {
            return graph.get(start).get(end);
        }
        
        visited.add(start);
        
        for (Map.Entry<String, Double> entry : graph.get(start).entrySet()) {
            String neighbor = entry.getKey();
            if (visited.contains(neighbor)) {
                continue;
            }
            double intermediateResult = dfs(graph, neighbor, end, visited);
            if (intermediateResult != -1.0) {
                return entry.getValue() * intermediateResult;
            }
        }
        
        return -1.0;
    }
    
    public static void main(String[] args) {
        EvaluateDivision solver = new EvaluateDivision();
        
        List<List<String>> equations = Arrays.asList(
            Arrays.asList("a", "b"),
            Arrays.asList("b", "c")
        );
        double[] values = {2.0, 3.0};
        List<List<String>> queries = Arrays.asList(
            Arrays.asList("a", "c"),
            Arrays.asList("b", "a"),
            Arrays.asList("a", "e"),
            Arrays.asList("a", "a"),
            Arrays.asList("x", "x")
        );
        
        System.out.println(Arrays.toString(solver.calcEquation(equations, values, queries)));
        // 输出: [6.0, 0.5, -1.0, 1.0, -1.0]
    }
}
